"""
编程规范：PEP-8
函数的设计尽量做到无副作用（side-effect）---> 不影响调用者
查找：
    ~ 顺序查找：列表无序
    ~ 二分查找：列表有序（折半查找）
排序：
    ~ 冒泡排序：两两比较，前面元素大于后面元素就交换位置
    ~ 归并排序：将待排序列表不断划分直到只有1个元素，再做有序合并
    ~ 快速排序：从待排序列表中选择枢轴（pivot），以枢轴为界对元素进行划分
Python内置的排序算法：sorted() ---> TimSort（多核版的归并排序）
"""
import random


def roll_dice(num=1):
    """摇色子
    :param num: 色子的数量
    :returns: 所有色子的点数和
    """
    total = 0
    for _ in range(num):
        total += random.randint(1, 6)
    return total


def seq_search(elems, key) -> int:
    """顺序查找
    :param elems: 待查找的列表
    :param key: 待查找的元素
    :returns: 在elems中找到key则返回key的索引, 否则返回-1
    """
    for index, elem in enumerate(elems):
        if elem == key:
            return index
    return -1


def bin_search(elems, key) -> int:
    """二分查找（列表有序且为升序）
    :param elems: 待查找的列表
    :param key: 待查找的元素
    :returns: 在elems中找到key则返回key的索引, 否则返回-1
    """
    start, end = 0, len(elems) - 1
    while start <= end:
        mid = (start + end) >> 1
        if key < elems[mid]:
            end = mid - 1
        elif key > elems[mid]:
            start = mid + 1
        else:
            return mid
    return -1


def bubble_sort(items, *, gt=lambda x, y: x > y):
    """冒泡排序
    :param items: 待排序的列表
    :returns: 排好序的列表
    """
    items = items[:]
    for i in range(1, len(items)):
        swapped = False
        for j in range(0, len(items) - i):
            if gt(items[j], items[j + 1]):
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break
    return items


def merge(items1, items2, le=lambda x, y: x <= y):
    """将两个有序列表合并成一个新的有序列表
    :param items1: 有序列表
    :param items2: 有序列表
    :returns: 将items1和items2合并后的有序列表
    """
    items = []
    index1, index2 = 0, 0
    while index1 < len(items1) and index2 < len(items2):
        if le(items1[index1], items2[index2]):
            items.append(items1[index1])
            index1 += 1
        else:
            items.append(items2[index2])
            index2 += 1
    items += items1[index1:]
    items += items2[index2:]
    return items


def merge_sort(items, *, le=lambda x, y: x <= y):
    """归并排序
    :param items: 待排序的列表
    :returns: 排序后的列表
    """
    if len(items) <= 1:
        return items[:]
    mid = len(items) // 2
    left = merge_sort(items[:mid], le=le)
    right = merge_sort(items[mid:], le=le)
    return merge(left, right, le)


# 归并排序 - 分治法（divide-and-conquer)
# [35, 99, 12, 78, 55, 69, 40, 21]
# [35, 99, 12, 78], [55, 69, 40, 21]
# [35, 99], [12, 78], [55, 69], [40, 21]
# [35], [99], [12], [78], [55], [69], [40], [21]
# [35, 99], [12, 78], [55, 69], [21, 40]
# [12, 35, 78, 99], [21, 40, 55, 69]
# [12, 21, 35, 40, 55, 69, 78, 99]

# 快速排序
# [35, 99, 12, 78, 55, 69, 40, 21]
# [21, 12], [35], [78, 55, 69, 40, 99]
# [12], [21], [35], [40, 55, 69], [78], [99]
# [12], [21], [35], [40], [55, 69], [78], [99]
# [12], [21], [35], [40], [55], [69], [78], [99]

# if __name__ == '__main__':
#     nums = [35, 99, 12, 78, 55, 69, 40, 21]
#     # sorted_nums = bubble_sort(nums)
#     sorted_nums = merge_sort(nums)
#     print(nums)
#     print(sorted_nums)


class Person:
    """人"""

    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    # 让对象可以像函数一样调用（callable object）
    def __call__(self, greeting):
        print(f'{self.name}说: {greeting}')
    
    # 计算对象的哈希码
    def __hash__(self):
        return hash(self.name) + hash(self.age)
    
    # 判断对象的相等性
    def __eq__(self, other):
        return self.name == other.name and self.age == other.age

    def __repr__(self):
        return f'{self.name}: {self.age}'
    
    def __str__(self):
        return self.__repr__()


if __name__ == '__main__':
    person = Person('王大锤', 30)
    person('你好')
    persons = [
        Person('Wang', 25), Person('Lee', 19), Person('Liu', 30),
        Person('Zhang', 35), Person('An', 28), Person('Lee', 20)
    ]
    # sorted_persons = bubble_sort(persons, gt=lambda x, y: x.age > y.age)
    sorted_persons = merge_sort(persons, le=lambda x, y: x.name <= y.name)
    print(sorted_persons)
